#include <iostream>
#include <vector>
using namespace std;

struct Node{
    int data;
    int next;
}node[100000];

signed main()
{
    int b,n,k;
    cin>>b>>n>>k;
    vector<int> v;
    for(int i=0;i<n;i++){
        int t;
        cin>>t>>node[t].data>>node[t].next;
    }
    for(int i=b;i!=-1;i=node[i].next)    v.push_back(i);
    int cnt = 0;
    vector<int> ans;
    if(v.size()%k!=0){
        for(int i=v.size()-v.size()%k;i<v.size();i++)
            ans.push_back(v[i]);
    }
    for(int i=v.size()/k-1;i>=0;i--){
        for(int j=i*k;j<(i+1)*k;j++)
            ans.push_back(v[j]);
    }
    for(int i=0;i<ans.size()-1;i++)
        printf("%05d %d %05d\n",ans[i],node[ans[i]].data,ans[i+1]);
    printf("%05d %d -1\n",ans[ans.size()-1],node[ans[ans.size()-1]].data);
    return 0;
}
